package com.practice.linesweep;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class NearestPair {
	public double minDistance(int[][] p) {
		double min = Double.MAX_VALUE;
		int N = p.length;
		ArrayList<Point> points = new ArrayList<Point>();
		
		for (int i=0; i<N; i++) points.add(new Point(p[i][0], p[i][1]));
		Collections.sort(points, new Comparator<Point>() {
			public int compare(Point a, Point b) {
				return a.x - b.x;
			}
		});
		
		ArrayList<Point> processed = new ArrayList<Point>();
		processed.add(points.remove(0));
		
		while (!points.isEmpty()) {
			Point next = points.remove(0);
			while (!processed.isEmpty() && next.x > processed.get(0).x + min) {
				processed.remove(0);
			}
			
			for (Point i : processed) {
				if (i.y <= next.y + min && i.y >= next.y - min) {
					min = Math.min(min, Math.sqrt((i.x-next.x)*(i.x-next.x) + 
							(i.y-next.y)*(i.y-next.y)));
				}
			}
			
			processed.add(next);
		}
		
		return min;
	}
	
	private class Point {
		int x, y;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}
